% THIS IS AN EXAMPLE DOCUMENT FOR VLDB 2010
% based on ACM SIGPROC-SP.TEX VERSION 2.7
% Modified by  Gerald Weber <gerald@cs.auckland.ac.nz>


% This example *does* use the .bib file (from which the .bbl file
% is produced). REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you need to 'insert'  your .bbl file into
% your source .tex file so as to provide ONE 'self-contained' source file.

\documentclass{vldb}
\usepackage{times}
%\usepackage[english]{algorithm2e}
\usepackage{algorithm}
\usepackage{algpseudocode}
%\usepackage[named]{algo}
%\algref{<algorithm>}{<line>}
\newtheorem{theorem}{Theorem}
%\newcounter{Observation}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{Observation}[theorem]{Observation}
\def\candidate{{\cal C}}
\def\comment#1{}
\usepackage{graphicx}
\input{psfig}


\pagestyle{empty}

\usepackage{graphicx}

\begin{document}

% ****************** TITLE ****************************************

\title{Finding Semantics in Time Series}
%\subtitle{[Extended Abstract]
%\titlenote{A full version of this paper is available as\textit{Author's Guide to Preparing ACM SIG Proceedings Using \LaTeX$2_\epsilon$\ and BibTeX} at \texttt{www.acm.org/eaddress.htm}}}

% ****************** AUTHORS **************************************

% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additional authors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.

\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Peng Wang\\%\titlenote{Dr.~Trovato insisted his name be first.}\\
       \affaddr{Fudan University}\\
%       \affaddr{}\\
%       \affaddr{Wallamaloo, New Zealand}\\
       \email{pengwang5@fudan.edu.cn}
% 2nd. author
\alignauthor
Haixun Wang\\%\titlenote{The secretary disavows
%any knowledge of this author's actions.}\\
       \affaddr{Microsoft Research Asia}\\
%       \affaddr{P.O. Box 1212}\\
%       \affaddr{Dublin, Ohio 43017-6221}\\
       \email{haixunw@microsoft.com}
% 3rd. author
\alignauthor
Wei Wang\\%{\Large{\sf{\o}}}rv{$\ddot{\mbox{a}}$}ld\titlenote{This author is the
%one who did all the really hard work.}\\
       \affaddr{Fudan University}\\
%       \affaddr{1 Th{\large{\sf{\o}}}rv{$\ddot{\mbox{a}}$}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
       \email{weiwang1@fudan.edu.cn}
}


\maketitle

\begin{abstract}
  In order to understand a complex system, we start by analyzing its
  output or its log data. For example, we track a system's resource
  consumption (CPU, memory, message queues of different types, etc) to
  help avert system failures; we examine economic indicators to assess
  the severity of a recession; we monitor a patient's heart rate or
  EEG for disease diagnosis. Time series data is involved in many such
  applications. Much work has been devoted to pattern discovery from
  time series data, but not much has attempted to use the time series
  to unveil a system's internal dynamics.  In this paper, we go beyond
  learning patterns from time series data. We focus on obtaining a
  better understanding of its data generating mechanism, and we regard
  patterns and their temporal relations as organic components of the
  hidden mechanism. Specifically, we propose to model time series data
  using a novel pattern-based hidden Markov model (pHMM), which aims
  at revealing a global picture of the system that generates the time
  series data. We propose an iterative approach to refine pHMMs
  learned from the data. In each iteration, we use the current pHMM to
  guide time series segmentation and clustering, which enables us to
  learn a more accurate pHMM.  Furthermore, we propose three pruning
  strategies to speed up the refinement process. Empirical results on
  real datasets demonstrate the feasibility and effectiveness of the
  proposed approach.
\end{abstract}

\input{introduction2}

%\input{preliminary}
\input{initial}
\input{refine}

\input{Experiment_vldb}
\input{related}

\section{Conclusion}
\label{sec:conclusion}


In this paper, we reveal the dynamics of a complex system by
learning a pattern-based hidden Markov model from the time series
data generated by this system. The biggest difference between a pHMM
and a traditional HMM is that in pHMM, observations are not given,
but are learned from the data as well. We propose an approach that
learns the patterns (observations) and the model simultaneously.
Furthermore, three pruning strategies are proposed to speed up the
learning process. With pHMM, we are able to perform pattern based
tasks, such as trend prediction and general correlation detection.
Empirical results on real datasets demonstrate the feasibility and
effectiveness of the
proposed approach. % In our future work, we plan to extend it to
% multiple dimensional datasets, and stream applications.

{\renewcommand{\baselinestretch}{0.92}
\normalsize
\bibliographystyle{plain}
\bibliography{haixun}
}

\newpage
\appendix
\input{app1}
\input{app2}
\input{application}

\end{document}
